<?php
/**
 *  NOTE: Iterator methods iterate over the `fake' root element's children,
 *      not on the whole tree (eg to iterate all of its nodes, use toArray())
 *  NOTE: it's impossible to create a tree element manually w/o tree
 *
 */
class Yz_Tree_Default
    extends Yz_Class
    implements ArrayAccess, Countable, Iterator, Yz_Tree_Interface
{

    /** a pseudo-root element i.e. the element is not in the tree
     *  but all the elements at depth 1 are its children
     *
     */
    protected $rootElement;
    protected $tree = array();


    /********************************
     *       Public methods         *
     ********************************/


    /** create a new tree or branch
     *  The $rootElementId is the parentId of a branch's top element(s) if it's not 0
     *  @param int|null $rootElementId
     *
     */
    public function __construct($rootElementId=null)
    {
        debug();

        if (null === $rootElementId) {

            $rootElementId = 0;
        } else {
            assert('is_scalar($rootElementId)');
            if ('0' !== (string)$rootElementId) {
                $rootElementId = $this->adjustIndex($rootElementId);
            }
        }
        // fake root which is not present in the tree
        $this->rootElement = new Yz_Tree_Element($this, $rootElementId, null);
    }


    /** toString()
    *
    *   @return string
    */
    public function __toString()
    {
        $cl = $this->className();
        $count = $this->count();
        return "Object({$cl}[{$count}])";
    } // toString

    /********************************
     *      Iterator methods        *
     ********************************/

    /**
     * @return Yz_Tree_Element_Interface
     */
    public function current()
    {
        return $this->rootElement->current();
    } //

    /**
     * @return chainable
     */
    public function next()
    {
        $this->rootElement->next();
        return $this;
    } //

    /**
     * @return int|null
     */
    public function key()
    {
        return $this->rootElement->key();
    } //

    /**
     * @return bool
     */
    public function valid()
    {
        return $this->rootElement->valid();
    } //

    /**
     * @return Yz_Tree_Element_Interface
     */
    public function rewind()
    {
        $this->rootElement->rewind();
        return $this;
    } //


    /** create an undistributed (ie. no parent assigned) element in the tree
     *  @todo track the undistributed elements, to avoid operations on them ###
     *      the apply functions do that inherently
     *  @param int $id
     *  @param mixed $value
     *  @return Yz_Tree_Element_Interface
     */
    public function createElement($id, $value)
    {
        debug();
        $id = $this->adjustIndex($id);
        if (array_key_exists($id, $this->tree)) {
            throw new Yz_Exception("Element with id=$id already exists");
        }
        $el = new Yz_Tree_Element($this, $id, $value);
        $this->tree[$id] = $el;
        return $el;
    }


    /**
     *  apply callback recursively to each element of the tree (i.e. all descendants of the element)
     *  Note: the processing order depends on implementation
     */
    public function apply($callback)
    {
        debug();

        if( ! is_callable( $callback ) ) {
            throw new Yz_Exception_InvalidArgument();
        }
        return $this->_applyToElement($callback, null);
    }

    protected function _applyToElement($callback, $el)
    {
        if (null === $el) {
            $el = $this->rootElement;
        } else {
            call_user_func( $callback, $el );
        }
        foreach ($el->children() as $ch) {
            $this->_applyToElement($callback, $ch);
        }
        return $this;
    }

    /**
    *   @return bool
    */
    public function inTree( Yz_Tree_Element_Interface $el )
    {
        debug();
        $id = $el->id();
        return array_key_exists($id, $this->tree)
            && $this->tree[$id] === $el;
    }


    /** get the tree as indexed array
     *
     *  @return array
     */
    public function toArray()
    {
        debug();
        return $this->tree;
    }

    /**
     *  Each element of the input array should contain at least the id and parentId properties
     *  The order of elements in the input array must be such that elements' parents be known before
     *      the elements themselves. Otherwise, an exception is thrown.
     *
     *  @param array-type[array-type] $array
     *
     *  @throw Exception if element.id or element.parentId fail to validate as possible tree element IDs
     *  @throw Exception if input can not be converted to an array
     */
    public static function fromArray($array)
    {
        $input = Yz_Array::valueOf($array);

        // identify the root element
        $rootElement = current($input);
        if (! isset($rootElement['parentId'])) {
            throw new Yz_Exception("Missing the id property for element 0");
        }
        $rootElementId = $rootElement['parentId'];

        // create the tree
        $tree = new static($rootElementId);

        // create and assign elements
        foreach ($input as $i => $entry) {

            // ensure object-style property access and NULL for missing properties
            $val = new Yz_Hash($entry);

            // validate id
            $id = $val->id;
            if (null === $id) {
                throw new Yz_Exception("Missing the id property for element {$i}");
            }

            // validate parent id
            $parentId = $val->parentId;
            if ( null === $parentId ) {
                throw new Yz_Exception("Undefined parent element id for element #{$id}");
            }
            assert('is_scalar($parentId)');

            // identify the parent element
            if ($rootElementId == $parentId) { // not using strict equality
                $parent = $tree->rootElement;
            } else {
                $parent = $tree->offsetGet($parentId);
                if (null === $parent) {
                    debug("Missing parent element #{$parentId} for element #{$id}");
                    throw new Yz_Exception("Missing parent element #{$parentId} for element #{$id}");
                }
            }

            // create element and assign it to the parent
            $el = $tree->createElement($id, $entry);
            $parent->addChild($el);
        }
        return $tree;
    }

    /** isEmpty()
    *   @return bool
    */
    public function isEmpty()
    {
        return 0 === count( $this->tree );
    } // isEmpty


    /**
    *  Countable method
    *   @return int
    */
    public function count()
    {
        return count( $this->tree );
    }


    /**
    *  Alias for count()
    *   @return int
    */
    public function length()
    {
        return $this->count();
    }

    /*******************************
    ****   ArrayAccess methods   ***
    *******************************/

    /**
     *  apply callback recursively to each element of the tree (i.e. all descendants of the element)
     *      and obtain the result value
     *  Note: the processing order depends on implementation
     *  @param callback $callback : function(element, value) => newValue
     *  @param mixed(null) initial value
     *  @return mixed result value
     */
    public function reduce($callback, $initialValue=null)
    {
        debug();

        if( ! is_callable( $callback ) ) {
            throw new Yz_Exception_InvalidArgument();
        }
        return $this->_reduceElement($callback, null, $initialValue);
    }

    protected function _reduceElement($callback, $el, $value)
    {
        if (null === $el) {
            $el = $this->rootElement;
        } else {
            $value = call_user_func( $callback, $el, $value );
        }
        foreach ($el->children() as $ch) {
            $value = $this->_reduceElement($callback, $ch, $value);
        }
        return $value;
    }

    protected function adjustIndex($index)
    {
        return Yz_Int::testPositive($index);
    }

    /** test if the index exists in Tree
     *  @param string index (after adjustIndex)
     *  @return bool
     */
    protected function indexExists( $index )
    {
        return array_key_exists( $index, $this->tree );
    }

    /** the default getter is called after index verification
     *  @param string index
     *  @return mixed|null
     */
    protected function defaultGetter( $index )
    {
        if ($this->indexExists( $index )) {
            return $this->tree[$index];
        }
        return null;
    }

    /** the default setter is called after index verification
     *  @param string index
     *  @return chainable
     */
    protected function defaultSetter( $index, $value )
    {
        throw new Yz_Exception("Can not set values directly");
    }

    /** the default unsetter is called after index verification
     *  @param string index
     *  @return chainable
     */
    protected function defaultUnsetter( $index )
    {
        throw new Yz_Exception("Can not unset values directly");
    }

}
